#define  _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int size = nums.size();
        vector<int> dp(size);
        dp[0] = nums[0];
        int len = 1;

        function<int(int)> getPos = [&](int cur) {
            if (cur > dp[len - 1]) return len++;
            int l = 0, r = len - 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (dp[mid] < cur) l = mid + 1;
                else r = mid;
            }
            return l;
            };

        for (int i = 1; i < size; i++) {
            int cur = nums[i];
            int pos = getPos(cur);
            dp[pos] = cur;
        }

        return len;
    }
};